This application is based upon and claims the benefit of priority under 35 U.S.C. xc2xa7119 to Japanese Patent Application No. 2000-192358, filed Jun. 27, 2000, the entire contents of which are incorporated herein by reference.
1. Field of the Invention
The present invention relates to electronic watermark detection apparatus and methods. More specifically, the invention relates to apparatus and methods for detecting electronic watermarks in digital documents, even if the content of the digital documents has been subjected to distortion or other attempts to hide or destroy the watermarks.
2. Discussion of the Background
In recent years, electronic digital content, such as sound, music, active movies, and still pictures, have come to circulate widely. Much digital content is protected under copyright. In order to protect the copyright of the digital content, various electronic watermark methods are used.
An electronic watermark method comprises embedding an electronic watermark within the digital content so that detecting and extracting the digital watermark is difficult. According to the intended use, the electronic watermark indicates identification information of a copyright person or a user, rights information of a copyright owner, use conditions, secret information required at the time of use, copy control information, and so on.
The digital content in which the electronic watermark is embedded is often geometrically distorted by various normal operations of a user, or by intentional attack. As an example of user""s normal operations, there is a change of the display size of an image. As an example of intentional attack of the user, there is a distortion of an image.
With regard to the electronic watermark method, it is required that the electronic watermark does not disappear, is not altered, and is able to be extracted, even if geometrical distortion is provided to the digital content. The requirement is called robustness.
Generally, geometrical distortion is classified into global distortion and local distortion.
Global distortion is distortion of a whole image, and may be caused by scaling, rotating, and/or parallel displacing. Global distortion can be expressed as an affine transformation formula. FIG. 1 illustrates how an original image I becomes a distorted image Ixe2x80x2 by global distortion. A point a(x, y) of the original image I is displaced to a point axe2x80x2(xxe2x80x2, yxe2x80x2) of the distorted image Ixe2x80x2 by global distortion. In this case, scaling and rotating can be expressed with four parameters, each being a component a11, a12, a21, and a22 of a 2xc3x972 matrix. Parallel displacing can be expressed with two parameters (b1, b2). Therefore, global distortion can be expressed with the following formula with these six parameters a11, a 12, a21, a22, b1 and b2.                               (                                                                      x                  xe2x80x2                                                                                                      y                  xe2x80x2                                                              )                =                                            (                                                                                          a                      11                                                                                                  a                      12                                                                                                                                  a                      21                                                                                                  a                      22                                                                                  )                        ⁢                          xe2x80x83                        ⁢                          (                                                                    x                                                                                        y                                                              )                                +                      (                                                                                b                    1                                                                                                                    b                    2                                                                        )                                              (        1        )            
On the other hand, local distortion means distortion in which each pixel of the whole original image is displaced by a different 2-dimensional vector. FIG. 2 shows that an original image I becomes a distorted image Ixe2x80x2 by local distortion. Therefore, local distortion can be expressed with the following formula as 2-dimensional generalized-coordinate conversion.                               (                                                                      x                  xe2x80x2                                                                                                      y                  xe2x80x2                                                              )                =                  (                                                                      f                  ⁡                                      (                                          x                      ,                      y                                        )                                                                                                                        g                  ⁡                                      (                                          x                      ,                      y                                        )                                                                                )                                    (        2        )            
where functions f and g are arbitrary functions. Although geometrical distortion may also include clipping, for brevity its description is not specifically included here.
The position of each pixel of the distorted image provided by geometrical distortion displaces the position of each pixel of an original image. An example of a detection method of electronic watermarks with consideration to displacing position of a pixel is shown in U.S. Pat. No. 6,108,434 (Cox et al.).
The Cox et al. method finds a best corresponding shifting position by repeatedly comparing with a predetermined block of an original image, while shifting a position of a block of a distorted image little by little on the basis of the position of the predetermined block of the original image. If the distorted image is shifted based on the best corresponding shifting position, the distorted image is concluded to correspond to the original image. Thereby, the shifting position of the distorted image corresponding to a original image can be compensated, and the electronic watermark in the distorted image can then be detected.
The Cox et al method involves a large computational load for arithmetic calculations, since it is necessary to search for a large number of possible shifting positions. With regard to global distortion, as just to find the shifting position of a single arbitrary block, the Cox et al. method is considered to be an effective resolution method.
The geometrical distortion that a user performs on an image is local distortion in many cases. In practice, it is difficult to detect the shifting position of each pixel by local distortion.
In local distortion, since vectors of neighboring pixels are almost the same, neighboring pixels can be treated as a small block unit. Even if local distortion is treated as a small block unit, it is difficult in practice since the number of candidate block positions is a large and processing time becomes huge when using the Cox et al. method.
As explained above, a method for detecting electronic watermarks on local distorted images is not believed to be provided by known systems.
According to embodiments of the present invention, a method of determining a correspondence between patches in an original image having n patches, and patches in a distorted image that constitutes the original image distorted in accordance with local distortion, is provided. The method involves inputting predetermining affine parameters of one of the plurality of predetermined patches; setting the input predetermining affine parameters of the one of the plurality of patch as initial affine parameters for investigating a new patch; and investigating a correspondence of the new patch of the distorted image and the new patch of the original image by slightly modifying the set input predetermining affine parameters.
The invention also provides an embodiment of a method of determining a correspondence between patches in an original image having n patches, and patches in a distorted image that constitutes the original image distorted in accordance with local distortion. Embodiments of this method involve inputting predetermining affine parameters of an m-th patch for determining an (m+1)-th patch, wherein 1 less than m less than n; setting the input predetermining affine parameters of the m-th patch as initial affine parameters for investigating the (m+1)-th patch; and investigating a correspondence of the (m+1)-th patch of the distorted image and the (m+1)-th patch of the original image by slightly modifying the input predetermining affine parameters.
The invention further provides an embodiment of a method of detecting an electronic watermark in a distorted image that constitutes a distortion of an original image in which the electronic watermark is embedded. This method involves inputting the distorted image and comparison information, the comparison information including at least one of the original image or information used for embedding the electronic watermark; dividing a domain of the original image into a plurality of patches, based on the comparison information; inputting affine parameters of a predetermined patch from among the patches in the original image; on the basis of the affine parameters, extracting a patch candidate from the distorted image; using a predetermined electronic watermark detection method, judging whether the patch candidate in the distorted image adequately correlates with a neighboring patch in the original image that neighbors the predetermined patch; and when the judging indicates an adequate correlation, outputting a part of the electronic watermark obtained by the predetermined electronic watermark detection method.